package 每日一题;

import com.alibaba.fastjson.JSON;

import java.util.Arrays;

public class No34查找升序数组中元素始末下标 {

    /**
     * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
     *
     * 如果数组中不存在目标值 target，返回 [-1, -1]。
     *
     * 进阶：
     *
     * 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
     *  
     *
     * 示例 1：
     *
     * 输入：nums = [5,7,7,8,8,10], target = 8
     * 输出：[3,4]
     * 示例 2：
     *
     * 输入：nums = [5,7,7,8,8,10], target = 6
     * 输出：[-1,-1]
     */


    //并不是好的解法

    /**
     * 二分法的left<right和 left<=right
     * 两者区别?
     * 1.若right=nums.length 那么就是 left<right
     * 2.若right=nums.length-1 那么就是 left<=right
     * 关键就是在于右指针是否可取
     */
    public static int[] searchRangeBad(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
        while (left<=right){
            //1.先找到目标元素,然后再开始第二步

            int mid=(left+right)/2;//找到中点下标
            int number=nums[mid];

            if(number>target){
                //当前位置元素大了,右指针移到mid
                right=mid-1;
            }else if(number<target){
                //当前位置元素小了,左指针移到mid
                left=mid+1;
            }else{
                //开始第二步
                //mid已经是目标元素了,然后开始两边扩散
                left=0;
                right=mid;//如果这里减1可能会超边界
                int result1=0;
                //左二分
                while (left<=right){

                    int mid2=(left+right)/2;//找到中点下标
                    int number2=nums[mid2];
                    //{5,7,7,8,8,8,10}
                    if(number2==target&&(mid2-1==-1||number2!=nums[mid2-1])){
                        result1=mid2;
                        break;
                    }
                    //继续找,小于的情况/等于的情况
                    if(number2==target){
                        //等于的情况,右指针往左
                        right=mid2-1;
                    }else{
                        //小于了,左指针往右
                        left=mid2+1;
                    }
                    if(left>=right)//没找到第二个
                        result1=mid;
                }
                left=mid;//如果这里加1,可能会超出边界
                right=nums.length-1;
                int result2=0;
                //右二分
                //{5,7,7,8,8,8,10}
                while (left<=right){

                    int mid2=(left+right)/2;//找到中点下标
                    int number2=nums[mid2];

                    if(number2==target&&(mid2+1==nums.length||number2!=nums[mid2+1])){
                        result2=mid2;
                        break;
                    }
                    //继续找,大于的情况/等于的情况
                    if(number2==target){
                        //等于的情况,左指针往右
                        left=mid2+1;
                    }else{
                        //大于了,右指针往左
                        right=mid2-1;
                    }
                    if(left>=right)
                        result2=mid;
                }
                return new int[]{result1,result2};
            }
        }
        return new int[]{-1,-1};
    }

    //weiwei哥版本的题解
    public int[] searchRange(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) {
            return new int[]{-1, -1};
        }

        int firstPosition = findFirstPosition(nums, target);
        if (firstPosition == -1) {
            return new int[]{-1, -1};
        }

        //右边是一定会存在的,至少是first的结果
        int lastPosition = findLastPosition(nums, target);
        return new int[]{firstPosition, lastPosition};
    }

    private int findFirstPosition(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 小于一定不是解
            if (nums[mid] < target) {
                // 下一轮搜索区间是 [mid + 1, right]
                left = mid + 1;
            } else if (nums[mid] > target) {
                // nums[mid] > target，下一轮搜索区间是 [left, mid - 1]
                right = mid - 1;
            } else {
                /**
                 * 需要包括mid,防止找到的丢失
                 */
                // 下一轮搜索区间是 [left, mid]
                right = mid;
            }
        }
        if (nums[left] == target) {
            return left;
        }
        return -1;
    }

    private int findLastPosition(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] > target) {
                // 下一轮搜索区间是 [left, mid - 1]
                right = mid - 1;
            } else if (nums[mid] < target){
                // nums[mid] < target，下一轮搜索区间是 [mid + 1, right]
                left = mid + 1;
            } else {
                // 下一轮搜索区间是 [mid, right] 防止丢失
                left = mid;
            }
        }
        //右边是一定会存在的,至少是first的结果
        return left;
    }

    public static void main(String[] args) {
        int[] nums=new int[]{1,4};
        int []result=searchRangeBad(nums,4);
        System.out.println(JSON.toJSONString(result));
    }

}
